/*
https://leetcode-cn.com/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode-bfcoj/
 */
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map=new HashMap<>();
        Stack<Integer> stack=new Stack<>();
        for (int i=nums2.length-1;i>=0;i--){
            int num=nums2[i];
            while (!stack.isEmpty()&&num>stack.peek()){
                stack.pop();
            }
            map.put(num,stack.isEmpty()?-1:stack.peek());
            stack.push(num);
        }
        for (int i=0;i<nums1.length;i++){
            nums1[i]=map.get(nums1[i]);
        }
        return nums1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution496().nextGreaterElement(new int[]{4,1,2},new int[]{1,3,4,2})[1]);
    }
}
